/*
**    Copyright (C) 2003-2011 Institute for Systems Biology
**                            Seattle, Washington, USA.
**
**    This library is free software; you can redistribute it and/or
**    modify it under the terms of the GNU Lesser General Public
**    License as published by the Free Software Foundation; either
**    version 3 of the License, or (at your option) any later version.
**
**    This library is distributed in the hope that it will be useful,
**    but WITHOUT ANY WARRANTY; without even the implied warranty of
**    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
**    Lesser General Public License for more details.
**
**    You should have received a copy of the GNU Lesser General Public
**    License along with this library; if not, write to the Free Software
**    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA
*/

package org.systemsbiology.util;

/**
 * Created by IntelliJ IDEA.
 * User: anorberg
 * Date: 7/14/11
 * Time: 2:57 PM
 * To change this template use File | Settings | File Templates.
 */

import org.systemsbiology.iteration.IterableFromIterator;
import org.systemsbiology.iteration.IteratorConverter;

import java.io.PrintWriter;
import java.io.Serializable;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;

/**
 * A class for binning double values into fixed-size buckets, generally for counting basic histograms.
 */
public class HistoCounter implements Iterable<HistoCounter.BinRecord>, Serializable {

    private double center;
    private double binSize;
    private double halfBin;
    private double min;
    private double max;
    private boolean hasNaN = false;
    private Clicker<Integer> counters;

    /**
     * Construct a HistoCounter with the specified center and bin size.
     * @param center Center for the 0th bin. Bin indexes can (and, in fact, are expected to) go negative, so this
     *               doesn't have to be a prediction for the low end of your data set.
     * @param binsz  Size of each bin.
     */
    public HistoCounter(double center, double binsz) {
        if(Double.isNaN(center) || Double.isInfinite(center)){
            throw new IllegalArgumentException("Transfinite value for center bin: " + center);
        }
        if(Double.isNaN(binsz) || Double.isInfinite(binsz)){
            throw new IllegalArgumentException("Transfinite value for bin size: " + binsz);
        }
        if(binsz == 0.0){
            throw new IllegalArgumentException("Bin size of zero is insensible");
        }
        this.min = this.max = this.center = center;
        this.binSize = binsz;
        counters = new Clicker<Integer>();
        halfBin = (binSize / 2); //adjustment to move from center to line at 0
    }

    /**
     * Construct a HistoCounter with the specified bin size, centered on 0.
     * @param binsize  Size of each bin.
     */
    public HistoCounter(double binsize){
        this(0, binsize);
    }

    /**
     * Copy constructor.
     * @param o HistoCounter to copy.
     */
    public HistoCounter(HistoCounter o){
        this.center = o.center;
        this.binSize = o.binSize;
        this.halfBin = o.halfBin;
        this.min = o.min;
        this.max = o.max;
        this.hasNaN = o.hasNaN;
        this.counters = new Clicker<Integer>(o.counters);
    }
    /**
     * Find which bin a given value would be in.
     * @param x Value to search for.
     * @return Bin index for the given double. null is the bin index of NaN. If the input is not NaN,
     *         the bin index is guaranteed to not be null.
     */
    public Integer index(double x){
        double norm = x - center + halfBin;
        double bin = norm / binSize;
        if(bin < 0.0){
            bin -= 1;   //to avoid double-size zero bin
        }
        return (int)bin; //integer rounding does what we want here
    }

    /**
     * Find the range of values that will be dropped into a given bin. Bin resolution puts the closer-to-center value
     * in the current bin, and the further-from-center value in the next bin. The center bin loses its higher-valued
     * line call. This is a side effect of double arithmetic and integer rounding that would require an inane amount
     * of code to avoid, especially since instability of floating-point values is much more likely to decide the
     * exact bin hit in these situations anyway.
     * @param binID Bin ID to find the range of.
     * @return a pair of Double values, representing the low and high extent of the bin.
     */
    public Pair<Double, Double> range(Integer binID){
        if(binID == null){
            return Pair.makePair(Double.NaN, Double.NaN); //null is the NaN sentinel!
        }
        double binCenter = binID * binSize + center;
        return Pair.makePair(binCenter - halfBin, binCenter + halfBin);
    }

    /**
     * Add a value to the histogram. Increments the count for the corresponding value's bucket.
     * @param x Value to add.
     */
    public void tally(double x){
        if(Double.isNaN(x)){
            hasNaN = true;
            counters.up(null);
            return;
        }
        if(x < min){min = x;}
        if(x > max){max = x;}
        counters.up(index(x));
    }

    /**
     * Look up how many elements are in the bucket for a particular value. Does not add the value to the histogram.
     * @param x Value to use as the basis for a lookup.
     * @return Number of elements in the same bucket as that value would be placed in.
     */
    public int countPeers(double x){
        return countBucket(index(x));
    }

    /**
     * Retrieve the number of elements in the bucket of this ID number. Null is the ID number for the bucket into
     * which all NaN values are placed.
     * @param bucket Integer representing a bucket ID. Null is a bucket ID.
     * @return The number of elements in that bucket.
     */
    public int countBucket(Integer bucket){
        return counters.get(bucket);
    }

    private static boolean veryNear(double... values){
        double maxUlp = 0;
        double max = Double.NEGATIVE_INFINITY;
        double min = Double.POSITIVE_INFINITY;
        for(double d: values){
            maxUlp = Math.max(maxUlp, Math.ulp(d));
            max = Math.max(max, d);
            min = Math.min(min, d);
        }
        return (max-min) < (2*maxUlp);
    }

    /**
     * Add the observations of another HistoCounter to this HistoCounter. Parameter HistoCounter is unchanged;
     * this one is heavily modified. Bin configuration must be compatable: same width, centered on an even multiple.
     * @param o HistoCounter to add in.
     */
    public void add(HistoCounter o){
        if(binSize != o.binSize){
            throw new IllegalArgumentException("Bin width non-equal.");
        }
        if(center != o.center){
            double centerDiff = center - o.center;
            double offset = centerDiff / binSize;
            if(!veryNear(Math.round(offset), offset)){
                throw new IllegalArgumentException("Bins not aligned.");
            }
        }

        //at this point, we know the histograms are compatible
        for(BinRecord bin : new IterableFromIterator<BinRecord>(o.populatedBinIterator())){
            Integer target = index((bin.getLowRange() + bin.getHighRange()) / 2);
            counters.put(target, counters.get(target) + bin.count);
        }
    }


    /**
     * Sums the contents of this HistoCounter with another HistoCounter and returns a new one with the summed values.
     * Neither this HistoCounter nor the added HistoCounter is modified; the new result is an independent copy. Bin
     * configuration must be compatable: same width, centered on an even multiple. The new HistoCounter will have
     * the same bin width as this.
     * @param o HistoCounter to add.
     * @return a new histoCounter, with its values initialized to the sum of the two HistoCounters.
     */
    public HistoCounter plus(HistoCounter o){
        HistoCounter ret = new HistoCounter(this);
        ret.add(o);
        return ret;
    }

    /**
     * Class that represents the contents of a bin.
     */
    public static class BinRecord implements Comparable<BinRecord>{
        private final double low, high;
        private final int count;

        /**
         * Constructs a bin record.
         * @param range Low and high range for this bin.
         * @param tally Number of elements in this bin.
         */
        public BinRecord(Pair<Double, Double> range, int tally){
            count = tally;
            low=range.first;
            high=range.second;
        }

        /**
         * Provides a nicely descriptive string of this object.
         * @return "Bin ([low], [high]) with [count] items"
         */
        public String toString(){
            return "Bin ("+ low + ", " + high + ") with " + count + " items";
        }

        /**
         * Retrieve the low extent of this bin range.
         * @return the low extent of the range.
         */
        public double getLowRange(){
            return low;
        }

        /**
         * Retrieve the high extent of this bin range.
         * @return the high extent of the range.
         */
        public double getHighRange(){
            return high;
        }

        /**
         * Retrieve the number of elements in the bin.
         * @return the count of elements in this bin.
         */
        public int getCount(){
            return count;
        }

        /**
         * Represent the bin as a record in a tab-seprated table, using a Low-High-Count schema.
         * @return "[low]\t[high]\t[count]"
         */
        public String asTSVRow(){
            return low + "\t" + high + "\t" + count;
        }

        /**
         * Provides a total order over all BinRecord objects. Consistent with equals, including bins with NaN
         * as part of (or both extents of) the range. Sorts by low range, then high range, then count.
         * @param o Bin record to compare against.
         * @return as per the general contract of compareTo.
         */
        public int compareTo(BinRecord o){
            if(this.low != o.low && !(Double.isNaN(this.low) && Double.isNaN(o.low))){
                if(Double.isNaN(this.low)) return 1;
                if(this.low > o.low) return 1;
                return -1;
            }
            if(this.high != o.high && !(Double.isNaN(this.high) && Double.isNaN(o.high))){
                if(Double.isNaN(this.low)) return 1;
                if(this.high > o.high) return 1;
                return -1;
            }
            if(this.count < o.count) return -1;
            if(this.count > o.count) return 1;
            return 0;
        }

        /**
         * Helper method to perform a double check for equality (which is sort of a ridiculous idea to begin with)
         * that handles NaN in special ways.
         * @param x First value to compare for equality.
         * @param y Second value to comapre for equality.
         * @return Whether or not x == y || both are NaN.
         */
        private static boolean nanEqual(double x, double y){
            return (x == y) || (Double.isNaN(x) && Double.isNaN(y));
        }

        /**
         * Value equality comparison consistent with compareTo's total ordering and the hash function. NaN values
         * are considered equal, rather than unequal, because they are a legal value for bins and equality
         * is meaningful in this case.
         * @param o Object to check for equality with.
         * @return as per the general contract of a deep equals.
         */
        public boolean equals(Object o){
            if(o == null) return false;
            if(o.getClass() != getClass()) return false;
            BinRecord otherBin = (BinRecord)o;
            return nanEqual(low, otherBin.low) && nanEqual(high, otherBin.high) && (count == otherBin.count);
        }

        /**
         * Hash function.
         * @return A hash code for this object.
         */
        public int hashCode(){
            long partial = Double.doubleToLongBits(low) ^ Double.doubleToLongBits(high);
            int foo = (int) partial;
            int bar = (int) (partial >> 32);
            return foo + bar + count;
        }
    }

    /**
     * Internal class to perform iteration over the entire observed range of values, including empty bins between and
     * the NaN bin, if nonempty. Bins are ordered, with the NaN bin last.
     */
    private class BinIterator implements Iterator<BinRecord> {
        private int currentBin;
        private int maxBin;
        private boolean nanBin;

        public BinIterator(){
            currentBin = index(min);
            maxBin = index(max);
            nanBin = hasNaN;
        }

        public synchronized boolean hasNext(){
            return nanBin || (currentBin <= maxBin);
        }

        public synchronized BinRecord next(){
            if(currentBin > maxBin){
                if(nanBin){
                    nanBin = false;
                    return new BinRecord(range(null), countBucket(null));
                }
                throw new NoSuchElementException("BinIterator run past populated bins");
            }
            return new BinRecord(range(currentBin), countBucket(currentBin++));
        }

        public void remove(){
            throw new UnsupportedOperationException("BinIterator does not support remove");
        }
    }

    /**
     * Provides an iterator over the entire observed range of values, including empty bins between the first and last
     * populated bin. Even if the center bin is empty, it will always be included, and may be one of the edges.
     * Bins are in sorted order, with NaN last.
     * @return an iterator yielding all bins in the range that this HistoCounter has observed, considering the
     *         center to always be observed. (Thus, there will always be at least one bin.) A NaN bin will be
     *         returned if and only if at least one NaN value has been tallied.
     */
    public Iterator<BinRecord> iterator(){
        return new BinIterator();
    }

    /**
     * Provides an iterator over only populated bins, with no order guaranteed. (This is, in fact, backed by
     * a hash map.) The NaN bin will be provided if and only if it is nonempty, like all other bins. There is
     * no guarantee that the center bin will be returned; it will be skipped if it is empty. Like all
     * hash-based iterators, no guarantees of order or stability of order are made.
     * @return an iterator that visits all populated bins while skipping all bins with 0 elements.
     */
    public Iterator<BinRecord> populatedBinIterator(){
        return new IteratorConverter<Pair<Integer, Integer>, BinRecord>(counters.iterator()){
            public BinRecord convert(Pair<Integer, Integer> source){
                return new BinRecord(range(source.first), source.second);
            }
        };
    }

    /**
     * Dumps the entire range of bins in a tab-separated (low-high-count) format onto the specified PrintWriter.
     * @param output PrintWriter to dump onto.
     */
    public void print(PrintWriter output){
        for(BinRecord record : this){
            output.println(record.asTSVRow());
        }
        output.flush();
    }

    /**
     * Hi, I'm a HistoCounter!
     * @return "HistoCounter centered at [center] with bin width [bin width]"
     */
    public String toString(){
        return "HistoCounter centered at " + center + " with bin width " + binSize;
    }

}
